package com.caoyanan.algorithm.question.zuoTraining.training003.class07;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;
import com.caoyanan.algorithm.question.zuoTraining.struct.UnionFind;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;


/**
 *
 * 一个数组中，如果两个数的最小公共因子大于1，则认为这两个数之间有通路
 * 返回数组中，有多少个独立的域
 * @author: caoyanan
 * @time: 2021/5/20 5:13 下午
 */
public class Question05_ArrayIndependentDomainNumber {

    public static void main(String[] args) {

        int count = 100000;
        for (int i = 0; i < count; i++) {
            int[] arr = LogarithmInputGenerator.getInstance().generateRandomArray(50, 1000);
            int independentNumber = loopJudge(arr);
            int number2 = primeFactor(arr);
            if (independentNumber != number2) {
                System.out.printf("数组 %s 不连通的域个数为 %s %s\n", Arrays.toString(arr), independentNumber, number2);
            }
        }
    }

    /**
     * 质数因子判断
     * @param arr
     * @return
     */
    private static int primeFactor(int[] arr) {
        UnionFind unionFind = new UnionFind(arr);

        Map<Integer, Integer> primeFactorMap = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            int sqrt = (int) Math.sqrt(arr[i]);
            for (int primeFactor = 1; primeFactor <= sqrt; primeFactor++) {
                if (arr[i] % primeFactor != 0) {
                    continue;
                }
                unionPrimeFactory(unionFind, primeFactorMap, primeFactor, arr[i]);
                unionPrimeFactory(unionFind, primeFactorMap, arr[i] / primeFactor, arr[i]);
            }
        }
        return unionFind.size();
    }

    private static void unionPrimeFactory(
            UnionFind unionFind, Map<Integer, Integer> primeFactorMap, int primeFactor, int num) {
        if (primeFactor == 1) {
            return;
        }
        Integer integer = primeFactorMap.get(primeFactor);
        if (Objects.isNull(integer)) {
            primeFactorMap.put(primeFactor, num);
            return;
        }

        unionFind.union(num, integer);
    }

    /**
     * 循环判断，时间复杂度 O(n^2)
     * @param arr
     * @return
     */
    private static int loopJudge(int[] arr) {

        UnionFind unionFind = new UnionFind(arr);
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                int gcd = gcd(arr[i], arr[j]);
                if (gcd != 1) {
                    unionFind.union(arr[i], arr[j]);
                }
            }
        }
        return unionFind.size();
    }

    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }


}
